package chapter20;

/**
 * vanEmdeBoas树-vEB树
 * <p>
 * 对比proto_vEB区别是每个vEB结构维护了最大值max/最小值min，可以进行区间的判断，减少递归的次数
 */
public class Tree_vEB {

    public static int successor(vEB V, int x) {
        if (V.u == 2) {
            if (x == 0 && V.max == 1) { // max就是大于当前值
                return 1;
            }
            return -1;
        } else if (V.min != -1 && x < V.min) { // 如果不是最小的结构，但是比最小值还要小，则直接返回最小值的，将不进行递归查找
            return V.min;
        } else {
            // 如果存在最大值，并且x在簇中的位置小于最大值的位置，如果小于最大值大于最小值则确定在当前簇中，则进行查找，然后计算
            int maxLow = maximum(V.cluster[high(V, x)]);
            if (maxLow != -1 && low(V, x) < maxLow) {
                int offset = successor(V.cluster[high(V, x)], low(V, x));
                return index(V, high(V, x), offset);
            } else {
                // 否则不在上述簇中，常规递归查找
                int succCluster = successor(V.summary, high(V, x));
                if (succCluster == -1) {
                    return -1;
                } else {
                    int offset = minimum(V.cluster[succCluster]);
                    return index(V, succCluster, offset);
                }
            }
        }
    }

    public static int predecessor(vEB V, int x) {
        if (V.u == 2) {
            if (x == 1 && V.min == 0) { //
                return 0;
            }
            return -1;
        } else if (V.max != -1 && x > V.max) { //
            return V.max;
        } else {
            // 如果小于最大值并大于最小值，则确定在当前簇中，找到就直接计算
            int minLow = minimum(V.cluster[high(V, x)]);
            if (minLow != -1 && low(V, high(V, x)) > minLow) {
                int offset = predecessor(V.cluster[high(V, x)], low(V, x));
                return index(V, high(V, x), offset);
            } else {
                int preCluster = predecessor(V.summary, high(V, x));
                // 如果summary中不存在，但是又大于最小值，证明在更前面的节点，返回当前的min减少递归
                if (preCluster == -1) {
                    if (V.min != -1 && x > V.min) {
                        return V.min;
                    } else {
                        return -1;
                    }
                } else {
                    int offset = maximum(V.cluster[preCluster]);
                    return index(V, preCluster, offset);
                }
            }
        }
    }

    /**
     * 初始化最大值最小值
     */
    public static void emptyInsert(vEB V, int x) {
        V.min = x;
        V.max = x;
    }

    public static void insertTree_vEB(vEB V, int x) {
        // 存在则不插入
        if (member(V, x)) {
            return;
        }
        insert(V, x);
    }

    private static void insert(vEB V, int x) {
        if (V.min == -1) {
            emptyInsert(V, x);
        } else {
            if (x < V.min) {
                int temp = V.min;
                V.min = x;
                x = temp;
            }
            if (V.u > 2) {
                if (minimum(V.cluster[high(V, x)]) == -1) {
                    insert(V.summary, high(V, x));
                    emptyInsert(V.cluster[high(V, x)], low(V, x));
                } else {
                    insert(V.cluster[high(V, x)], low(V, x));
                }
            }
            if (x > V.max) {
                V.max = x;
            }
        }
    }

    public static void deleteTree_vEB(vEB V, int x) {
        if (!member(V, x)) {
            return;
        }
        delete(V, x);
    }

    private static void delete(vEB V, int x) {
        // 说明当前节点只有一个元素,直接最大最小值设置为-1
        if (V.min == V.max) {
            V.min = -1;
            V.max = -1;
        } else if (V.u == 2) {
            // 如果存在最小的vEB
            if (x == 0) {
                V.min = 1;
            } else {
                V.min = 0;
            }
            V.max = V.min;
        } else {
            // 维护最小值
            if (x == V.min) {
                int firstCluster = minimum(V.summary);
                x = index(V, firstCluster, minimum(V.cluster[firstCluster]));
                V.min = x;
            }
            delete(V.cluster[high(V, x)], low(V, x));
            // 如果没有数值，递归维护每个summary的最小值最大值
            if (minimum(V.cluster[high(V, x)]) == -1) {
                delete(V.summary, high(V, x));
                // 因为没有维护最大值，所以如果删除的就是最大值，则找到新的值进行赋值，不存在就将最小值给最大值
                if (x == V.max) {
                    int summaryMax = maximum(V.summary);
                    if (summaryMax == -1) {
                        V.max = V.min;
                    } else {
                        V.max = index(V, summaryMax, maximum(V.cluster[summaryMax]));
                    }
                }
            } else if (x == V.max) { // 如果还存在值则重新计算最大值
                V.max = index(V, high(V, x), maximum(V.cluster[high(V, x)]));
            }
        }
    }

    public static vEB createTree_vEB(int u) {
        vEB V = new vEB();
        create(V, u);
        return V;
    }

    private static void create(vEB V, int u) {
        if (u == 2) {
            V.u = u;
            V.A = new int[u];
            return;
        }
        int u1 = (int) Math.sqrt(u);
        V.u = u;
        V.summary = new vEB();
        create(V.summary, u1);
        V.cluster = new vEB[u1];
        for (int i = 0; i < u1; i++) {
            V.cluster[i] = new vEB();
            create(V.cluster[i], u1);
        }
    }

    public static boolean member(vEB V, int x) {
        // 直接判断与最大值最小值是否相等
        if (x == V.min || x == V.max) {
            return true;
        } else if (V.u == 2) {
            return false;
        } else {
            return member(V.cluster[high(V, x)], low(V, x));
        }
    }

    public static int minimum(vEB V) {
        return V.min;
    }

    public static int maximum(vEB V) {
        return V.max;
    }

    private static int high(vEB V, int x) {
        return (int) (x / Math.sqrt(V.u));
    }

    private static int low(vEB V, int x) {
        return (int) (x % Math.sqrt(V.u));
    }

    private static int index(vEB V, int x, int y) {
        return (int) (x * Math.sqrt(V.u) + y);
    }

    public static class vEB {
        public int u;
        public vEB summary;
        public vEB[] cluster;
        public int[] A;
        public int n;
        public int max = -1;
        public int min = -1;
    }
}
